package com.linyaonan.leetcode.medium._658;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

/**
 * 给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
 *
 * 整数 a 比整数 b 更接近 x 需要满足：
 *
 * |a - x| < |b - x| 或者
 * |a - x| == |b - x| 且 a < b
 *
 *
 * 示例 1：
 *
 * 输入：arr = [1,2,3,4,5], k = 4, x = 3
 * 输出：[1,2,3,4]
 * 示例 2：
 *
 * 输入：arr = [1,1,2,3,4,5], k = 4, x = -1
 * 输出：[1,1,2,3]
 *
 *
 * 提示：
 *
 * 1 <= k <= arr.length
 * 1 <= arr.length <= 10^4
 * arr 按 升序 排列
 * -10^4 <= arr[i], x <= 10^4
 *
 * @author: Lin
 * @date: 2024/10/7
 */
public class FindKClosestElements {

    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        // 1. 边界情况 目标值比最小值小，目标值比最大值大
        if (x <= arr[0]) {
            return build(arr, 0, k - 1);
        } else if (x >= arr[arr.length - 1]) {
            return build(arr, arr.length - k, arr.length - 1);
        }
        // 2. 二分查找找到最左匹配的位置
        int i = binSearchGetLeftIndex(arr, x);
        int l = i - 1;
        int r = i;
        int count = 0;
        ArrayList<Integer> result = new ArrayList<>();
        while (count < k) {
            if (l >= 0 && r <= arr.length - 1 &&  Math.abs(arr[l] - x) <= Math.abs(arr[r] - x)) {
                result.add(arr[l]);
                l--;
            } else if (r <= arr.length - 1 && l >= 0 && Math.abs(arr[l] - x) > Math.abs(arr[r] - x)) {
                result.add(arr[r]);
                r++;
            } else {
                // 右边没有数值了
                if (r > arr.length - 1) {
                    result.add(arr[l]);
                    l--;
                } else if (l < 0) {
                    result.add(arr[r]);
                    r++;
                }
            }
            count++;
        }
        Collections.sort(result);

        return result;
    }

    private List<Integer> build(int[] arr, int start, int end) {
        List<Integer> list = new ArrayList<>();
        for (int i = start; i <= end; i++) {
            list.add(arr[i]);
        }

        return list;
    }

    /**
     * 最左匹配找到最接近目标值的索引
     * @param arr
     * @param target
     * @return
     */
    private int binSearchGetLeftIndex(int[] arr, int target) {

        int l = 0;
        int r = arr.length - 1;
        int result = 0;
        while (l <= r) {
            int m = (l + r) >>> 1;
            int temp = arr[m];
            if (temp == target) {
                result = m;
                r--;
            } else if (temp < target) {
                l++;
            } else {
                result = m;
                r--;
            }
        }

        return result;
   }

}
